package SwordFingerOffer;

import java.util.jar.JarEntry;

public class Q22_DeleteListNodeDesc {
    //删除链表倒数第n个节点
    public ListNode getKthFromEnd(ListNode head, int k) {
        //还是快慢指针
        //快慢指针间隔k个距离

        //一些边界考虑
        //倒数第0个 || 倒数第一个并且头结点无next
        if (k == 0 || (head.next == null && k == 1)) return null;

        //一些边界考虑
        ListNode fast = head.next;
        ListNode slow = head;

        //fast先走k步
        int n = k;
        while (n != 0 && fast != null){
            fast = fast.next;
            n --;
        }
        //倒数第n个左越过了头节点
        if (n > 0){
            //k == 1 就是刚好要删除头节点的情况
            if (n == 1){
                return head.next;
            }
            return head;
        }

        //快慢同步走 fast走到尾为止
        while (fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        //删除操作
        slow.next = slow.next.next;

        return head;
    }

    //获取倒数第n个节点
    public ListNode getKthFromEnd_(ListNode head, int k) {
        //还是快慢指针
        //快慢指针间隔k个距离
        if (k == 0) return null;
        //一些边界考虑
        //获取头节点的情况
        //倒数第一个并且头结点无next
        if (head.next == null && k == 1) return head;


        ListNode fast = head;
        ListNode slow = head;

        //fast先走k步
        int n = k;
        while (n != 0 && fast != null){
            fast = fast.next;
            n --;
        }
        //倒数第n个左越过了头节点
        if (n > 0){
            return null;
        }

        //快慢同步走 fast走到尾为止
        while (fast != null){
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }

}
